{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rearrange Characters to Make Target String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rearrangeCharacters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重排字符形成目标字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong> 开始的字符串 <code>s</code> 和 <code>target</code> 。你可以从 <code>s</code> 取出一些字符并将其重排，得到若干新的字符串。</p>\n",
    "\n",
    "<p>从 <code>s</code> 中取出字符并重新排列，返回可以形成 <code>target</code> 的 <strong>最大</strong> 副本数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"ilovecodingonleetcode\", target = \"code\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "对于 \"code\" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。\n",
    "对于 \"code\" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。\n",
    "形成的字符串分别是 \"ecod\" 和 \"code\" ，都可以重排为 \"code\" 。\n",
    "可以形成最多 2 个 \"code\" 的副本，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"abcba\", target = \"abc\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "选取下标为 0 、1 和 2 的字符，可以形成 \"abc\" 的 1 个副本。 \n",
    "可以形成最多 1 个 \"abc\" 的副本，所以返回 1 。\n",
    "注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 \"abc\" 的第 2 个副本。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"abbaccaddaeea\", target = \"aaaaa\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 \"aaaaa\" 的 1 个副本。\n",
    "可以形成最多 1 个 \"aaaaa\" 的副本，所以返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= target.length &lt;= 10</code></li>\n",
    "\t<li><code>s</code> 和 <code>target</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rearrange-characters-to-make-target-string](https://leetcode.cn/problems/rearrange-characters-to-make-target-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rearrange-characters-to-make-target-string](https://leetcode.cn/problems/rearrange-characters-to-make-target-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ilovecodingonleetcode\"\\n\"code\"', '\"abcba\"\\n\"abc\"', '\"abbaccaddaeea\"\\n\"aaaaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = float('inf')\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        t = Counter(target)\n",
    "        c = defaultdict(int)\n",
    "        for ch in s :\n",
    "            if ch in target :\n",
    "                c[ch]+= 1 \n",
    "        min_x = 0x3f3f3f3f\n",
    "        for k in t :\n",
    "            min_x = min(min_x , c[k]//t[k])\n",
    "        return min_x\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        result = 101\n",
    "        s, target = Counter(s), Counter(target)\n",
    "        for key in target:\n",
    "            result = min(result, s[key] // target[key])\n",
    "            if result == 0:\n",
    "                return 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        from collections import Counter,defaultdict\n",
    "        m = len(target)\n",
    "        n = len(s)\n",
    "        d = defaultdict(int)\n",
    "        d = {i:j for i,j in Counter(s).items() if i in target}\n",
    "        b = Counter(target)\n",
    "        return min(d.get(i,0)//j for i,j in b.items())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        targetcount = {}\n",
    "        for ch in target:\n",
    "            if ch not in targetcount:\n",
    "                targetcount[ch] = 1\n",
    "            else:\n",
    "                targetcount[ch] += 1\n",
    "        scount = {}\n",
    "        for ch in s:\n",
    "            if ch not in scount:\n",
    "                scount[ch] = 1\n",
    "            else:\n",
    "                scount[ch] += 1\n",
    "        res = []\n",
    "        for ch,v in targetcount.items():\n",
    "            if ch in scount:\n",
    "                # print(scount[ch])\n",
    "                res.append(scount[ch]//v)\n",
    "            else:\n",
    "                return 0\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ss = Counter(s)\n",
    "        tt = Counter(target)\n",
    "        n = len(s)\n",
    "        for x in tt:\n",
    "            n = min(n, ss[x] // tt[x])\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "\n",
    "        return min(cnt[k] // v for k, v in Counter(target).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = float('inf')\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cnt1 = Counter(s)\n",
    "        cnt2 = Counter(target)\n",
    "        ans = inf\n",
    "        for k, v in cnt2.items():\n",
    "            if k in cnt1:\n",
    "                ans = min(ans, cnt1[k]//v)\n",
    "            else:\n",
    "                return 0\n",
    "        return ans\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        count=0\n",
    "        ad={}\n",
    "        for i in s:\n",
    "            if i in target:\n",
    "                ad[i]=ad.get(i,0)+1\n",
    "        while True:\n",
    "            flag=True\n",
    "            for i in target:                \n",
    "                if i not in ad or ad[i]==0 :\n",
    "                    flag=False\n",
    "                    break\n",
    "                ad[i]-=1\n",
    "            if flag:\n",
    "                count+=1\n",
    "            else:\n",
    "                return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "            def have(target,list_s):\n",
    "                lenth = len(list_s)\n",
    "                for i in target:\n",
    "                    for j in range(len(list_s)):\n",
    "                        if i == list_s[j]:\n",
    "                            list_s.pop(j)\n",
    "                            break\n",
    "                if lenth - len(list_s) == len(target):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            res = 0\n",
    "            list_s = list(s)\n",
    "            while have(target,list_s):\n",
    "                res +=1\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        a = Counter(s)\n",
    "        b = Counter(target)\n",
    "        return min(a[i] // j for i, j in b.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cnt1=Counter(s)\n",
    "        cnt2=Counter(target)\n",
    "        f=1\n",
    "        ans=0\n",
    "        while True:\n",
    "            for i in cnt2:\n",
    "                if cnt1[i]<cnt2[i]:\n",
    "                    f=0\n",
    "                    break\n",
    "            if f==1:\n",
    "                ans+=1\n",
    "                for i in cnt2:\n",
    "                    cnt1[i]=cnt1[i]-cnt2[i]\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        s = Counter(s)\n",
    "        target = Counter(target)\n",
    "        return min(s[k] // target[k] for k in target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        d1,d2 = {},{}\n",
    "        for k in target:\n",
    "            if k not in d1:\n",
    "                d1[k] = 1\n",
    "            else:\n",
    "                d1[k] += 1\n",
    "        for k in s:\n",
    "            if k not in d2:\n",
    "                d2[k] = 1\n",
    "            else:\n",
    "                d2[k] += 1\n",
    "        res = 100       \n",
    "        for k in d1:\n",
    "            if k not in d2:\n",
    "                return 0\n",
    "            res = min(res, d2[k]//d1[k])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        # return min(Counter(s)[i] // v for i, v in Counter(target).items())\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        print(cnt_s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = float('inf')\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "      ans = inf\n",
    "      cnt_s = Counter(s)\n",
    "      for c, cnt in Counter(target).items():\n",
    "        ans = min(ans, cnt_s[c] // cnt)\n",
    "        if ans == 0:\n",
    "          return 0\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        dss,dst = Counter(s),Counter(target)\n",
    "        ans = float('inf')\n",
    "        for k in dst:\n",
    "            ans = min(ans,dss[k]//dst[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        t_map = {}\n",
    "        for t in target:\n",
    "            if t in t_map:\n",
    "                t_map[t] += 1\n",
    "            else:\n",
    "                t_map[t] = 1\n",
    "        s_map = {ss: 0 for ss in t_map.keys()}\n",
    "        for ss in s:\n",
    "            if ss in s_map:\n",
    "                s_map[ss] += 1\n",
    "        ans_list = []\n",
    "        for ss, val in s_map.items():\n",
    "            ans_list.append(val // t_map[ss])\n",
    "        return min(ans_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cs = Counter(s)\n",
    "        ct = Counter(target)\n",
    "        return min(cs[c]//n for c, n in ct.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        dic = Counter(s)\n",
    "        ans = 0\n",
    "        n = len(target)\n",
    "        while True:\n",
    "            a = 0\n",
    "            for c in target:\n",
    "                if dic[c] > 0:\n",
    "                    dic[c] -= 1\n",
    "                    a += 1\n",
    "                else:\n",
    "                    return ans\n",
    "            if a == n:\n",
    "                ans += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        lsts=list(s)\n",
    "        lsttarget=list(target)\n",
    "        anslst=[]\n",
    "        for i in lsttarget:\n",
    "            anslst.append(lsts.count(i)//lsttarget.count(i))\n",
    "        return min(anslst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        return min(Counter(s)[i] // v for i, v in Counter(target).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cnt1 = Counter(s)\n",
    "        cnt2 = Counter(target)\n",
    "        \n",
    "        \n",
    "            \n",
    "        return min(cnt1[c] // v for c, v in cnt2.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        for j in target:\n",
    "            if j not in s:\n",
    "                return 0\n",
    "        tmp = [0] * 26\n",
    "        for x in s:\n",
    "            tmp[ord(x) - ord(\"a\")] += 1\n",
    "        ans = 1000\n",
    "        for i in s:\n",
    "            if i in target:\n",
    "                ans = min(ans,tmp[ord(i) - ord(\"a\")] // target.count(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        tmp=Counter(s)\n",
    "        t=Counter(target)\n",
    "        res=100\n",
    "        for i,v in t.items():\n",
    "            res=min(res, tmp.get(i,0)//v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        #-----------------------------#\n",
    "        # 想到要满足最小\n",
    "        # 相对应的也要满足最大\n",
    "        # 在最大和最小中取最小值\n",
    "        # 才是局部最优到全局最优\n",
    "        #-----------------------------#\n",
    "        path = dict()\n",
    "        res = dict()#收集最后结果\n",
    "        temp_path = []\n",
    "        for tar in target:\n",
    "         if  (tar not in path.keys()):\n",
    "             path[tar] = 1\n",
    "         elif (tar in path.keys()):\n",
    "             path[tar] += 1\n",
    "        #print(path)\n",
    "        for ss in s:\n",
    "          if (ss in path.keys()) and (ss not in res.keys()):\n",
    "             res[ss] = 1\n",
    "          elif (ss in path.keys()) and (ss  in res.keys()):\n",
    "              res[ss] += 1\n",
    "        if len(path)!=len(res): return 0\n",
    "        for k,v in res.items():\n",
    "            temp_path.append(v)\n",
    "        temp_path = sorted(res.items(),key = lambda x:x[1])\n",
    "        _ = sorted(path.items(),key = lambda x:x[1])\n",
    "        print(path)\n",
    "        print(temp_path)\n",
    "        fast , l = 0,len(path)\n",
    "        for fast in range(l):\n",
    "            # 找到目标的长度\n",
    "            key,value = temp_path[fast]\n",
    "            tarvalue = path[key]\n",
    "            if value < tarvalue: return 0\n",
    "        #-----------------#\n",
    "        # 满足最小\n",
    "        #-----------------#\n",
    "        temp = temp_path[0]\n",
    "        key,value = temp\n",
    "        \n",
    "        #获取target对应的键数值\n",
    "        k,ele = _[0]\n",
    "        Min = value//ele\n",
    "        #if ele == 0: return 0\n",
    "        #-------------#\n",
    "        # 满足最大\n",
    "        #-------------#\n",
    "\n",
    "        temp = temp_path[-1]\n",
    "        key,value = temp\n",
    "        \n",
    "        #获取target对应的键数值\n",
    "        k,ele = _[-1]\n",
    "        Max = value//ele\n",
    "        return min(Max,Min)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        c1, c2 = Counter(s), Counter(target)\n",
    "        ans = len(s)\n",
    "        for k, v in c2.items():\n",
    "            ans = min(ans, c1[k] // c2[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        ans = 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            for ii in target:\n",
    "                if ii not in dic:\n",
    "                    flag = False\n",
    "                    break\n",
    "                else:\n",
    "                    dic[ii] -= 1\n",
    "                    if dic[ii] < 0:\n",
    "                        flag = False\n",
    "                        break\n",
    "            ans += 1\n",
    "\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_target = Counter(target)\n",
    "        counter_s = Counter(s)\n",
    "        \n",
    "        res = 0\n",
    "        while 1:\n",
    "            for k, v in counter_target.items():\n",
    "                if counter_s[k] >= v:\n",
    "                    counter_s[k] = counter_s[k] - v\n",
    "                else:\n",
    "                    return res\n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        return min(Counter(s).get(i, 0) // Counter(target)[i] for i in Counter(target).keys()) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        dic = Counter(s)\n",
    "        t = Counter(target)\n",
    "        ans = len(s)\n",
    "        for k, v in t.items():\n",
    "            ans = min(ans, dic[k] // v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for ch in target:\n",
    "            cnt[ch] += 1\n",
    "        \n",
    "        res = float('inf')\n",
    "        for k,v in cnt.items():\n",
    "            res = min(res,s.count(k)/v)\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            if i in target:\n",
    "                dic[i] = dic.get(i, 0) + 1\n",
    "        dt = {}\n",
    "        for i in target:\n",
    "            dt[i] = dt.get(i, 0) + 1\n",
    "        ans = []\n",
    "        for i in dt.keys():\n",
    "            if i in dic:\n",
    "                ans.append(dic[i] // dt[i])\n",
    "            else:\n",
    "                # target 里的元素，有的并不存在与 s里，那直接返回 0\n",
    "                return 0\n",
    "        return min(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        counter_s = Counter(s)\n",
    "        counter_t = Counter(target)\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in set(target):\n",
    "                counter_s[i] -= counter_t[i]\n",
    "                if counter_s[i] < 0:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        s_dict = collections.Counter(s)\n",
    "        tar_dict = collections.Counter(target)\n",
    "        minNum = float('inf')\n",
    "        for i in target:\n",
    "            minNum = min(minNum, s_dict[i] // tar_dict[i])\n",
    "        return minNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        tmp=Counter(s)\n",
    "        t=Counter(target)\n",
    "        res=100\n",
    "        for i,v in t.items():\n",
    "            if i not in tmp:\n",
    "                return 0\n",
    "            \n",
    "            res=min(res, tmp[i]//v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        fre1=Counter(s)\n",
    "        fre2=Counter(target)\n",
    "        res=0\n",
    "        keys=fre2.keys()\n",
    "        arr2=list(fre2.values())\n",
    "        arr1=[]\n",
    "        arr3=[]\n",
    "        for i in keys:\n",
    "            arr1.append(fre1[i])\n",
    "        print(arr1,arr2)\n",
    "        for i in range(len(arr1)):\n",
    "            arr3.append(arr1[i]//arr2[i])\n",
    "        return min(arr3)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnt_s = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnt_s[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        C = Counter(s)\n",
    "        res = inf\n",
    "        nC = Counter(target)\n",
    "        for it,i in nC.items():\n",
    "            res = min(res,C[it]//i)\n",
    "        return res if res<inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        h = {}\n",
    "        for w in target:\n",
    "            if w in h:\n",
    "                h[w] += 1\n",
    "            else:\n",
    "                h[w] = 1\n",
    "        for w in h.keys():\n",
    "            h[w] = (s.count(w)) // h[w]\n",
    "        return min(n for n in h.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = inf\n",
    "        cnts = Counter(s)\n",
    "        for c, cnt in Counter(target).items():\n",
    "            ans = min(ans, cnts[c] // cnt)\n",
    "            if ans == 0:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        return min(Counter(s)[i]//v for i,v in Counter(target).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        hash_map={}\n",
    "        count=0\n",
    "        for i in s:\n",
    "            if i not in hash_map:\n",
    "                hash_map[i]=1\n",
    "            else:\n",
    "                hash_map[i]+=1\n",
    "        while 1:\n",
    "            for i in target:\n",
    "                if i not in hash_map or hash_map[i]<1:\n",
    "                    return count\n",
    "                else:\n",
    "                    hash_map[i]-=1\n",
    "            count+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(s)\n",
    "        while True:\n",
    "            for c in target:\n",
    "                cnt[c] -= 1\n",
    "                if cnt[c] < 0:\n",
    "                    return ans\n",
    "            ans += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        hashmap1 =collections.defaultdict(int)\n",
    "        hashmap2 =collections.defaultdict(int)\n",
    "        res = float('inf')\n",
    "        for c in s:\n",
    "            hashmap1[c] += 1\n",
    "\n",
    "        for c in target:\n",
    "            hashmap2[c] += 1\n",
    "        return min(hashmap1[c] // v for c, v in hashmap2.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeCharacters(self, s: str, target: str) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for ch in target:\n",
    "            cnt[ch] += 1\n",
    "        \n",
    "        res = float('inf')\n",
    "        for k,v in cnt.items():\n",
    "            res = min(res,s.count(k)//v)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
